import java.util.*;

public class Solution923 {
    public int threeSumMulti(int[] arr, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        int m=1000000007;
        for (int i : arr) {
            map.put(i,map.getOrDefault(i,0)+1);
        }
        long ans=0;
        if (target%3==0){
            int t=map.getOrDefault(target/3,0);
            ans=((long)t*(t-1)*(t-2))/6%m;
        }
        Set<Integer> set=map.keySet();
        for (Integer integer : set) {
            if ((target-integer)%2==0 && integer*3!=target && map.containsKey((target-integer)/2)){
                int a=map.get(integer);
                int t=map.get((target-integer)/2);
                int b=t*(t-1)/2%m;
                ans=(ans+a*b%m)%m;
            }
        }
        List<Integer> list=new ArrayList<>(set);
        list.sort(Comparator.comparingInt(a -> a));
        for (int i=0;i<list.size();i++){
            for (int j=i+1;j<list.size();j++){
                int t=target-list.get(i)-list.get(j);
                if (t>list.get(j)) {
                    ans=(ans+map.get(list.get(i))*map.get(list.get(j))*map.getOrDefault(t, 0)%m)%m;
                }
            }
        }
        return (int)ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution923().threeSumMulti(new int[]{1,1,2,2,3,3,4,4,5,5},8));
    }
}
